Search for: All records

Abstract An $$n \times n$$ matrix with $$\pm 1$$ entries that acts on $${\mathbb {R}}^{n}$$ as a scaled isometry is called Hadamard. Such matrices exist in some, but not all dimensions. Combining number-theoretic and probabilistic tools, we construct matrices with $$\pm 1$$ entries that act as approximate scaled isometries in $${\mathbb {R}}^{n}$$ for all $$n \in {\mathbb {N}}$$. More precisely, the matrices we construct have condition numbers bounded by a constant independent of $$n$$. Using this construction, we establish a phase transition for the probability that a random frame contains a Riesz basis. Namely, we show that a random frame in $${\mathbb {R}}^{n}$$ formed by $$N$$ vectors with independent identically distributed coordinate having a nondegenerate symmetric distribution contains many Riesz bases with high probability provided that $$N \ge \exp (Cn)$$. On the other hand, we prove that if the entries are sub-Gaussian, then a random frame fails to contain a Riesz basis with probability close to $$1$$ whenever $$N \le \exp (cn)$$, where $c<C$ are constants depending on the distribution of the entries. 

Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching: Our algorithm associates each vertex with a signature vector using a multistage procedure and then matches a pair of vertices from the two graphs if their signature vectors are close to each other. We show that, for two Erdős–Rényi graphs with edge correlation $$1-\alpha$$, our algorithm recovers the underlying matching exactly with high probability when $$\alpha \le 1 / (\log \log n)^C$$, where $$n$$ is the number of vertices in each graph and $$C$$ denotes a positive universal constant. This improves the condition $$\alpha \le 1 / (\log n)^C$$ achieved in previous work. 

Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching: Our algorithm associates each vertex with a signature vector using a multistage procedure and then matches a pair of vertices from the two graphs if their signature vectors are close to each other. We show that, for two Erdős–Rényi graphs with edge correlation 1−α, our algorithm recovers the underlying matching exactly with high probability when α≤1/(loglogn)C, where n is the number of vertices in each graph and C denotes a positive universal constant. This improves the condition α≤1/(logn)C achieved in previous work.